package com.algorithm;

import java.util.Arrays;
import java.util.Random;

/**
 * 实验java的mergesort和quicksort
 */
public class NewSortTest {

    int in;
    public static void main(String[] args){

        NewSortTest test = new NewSortTest();
        Random rand = new Random();
        int count = 10000000;
        int range = 10000000;
        int[] unsorted = new int[count];
        for(int i = 0; i < count;i ++){
            unsorted[i] = rand.nextInt(range);
        }

        long before = System.currentTimeMillis();
        //test.mergeSort(unsorted);
        //test.quickSort(unsorted);
        //Arrays.sort(unsorted);
        long after = System.currentTimeMillis();
        //System.out.println(Arrays.toString(unsorted));
        System.out.println(after - before);
    }

    public void quickSort(int[] unSorted){
        quickSort(unSorted,0,unSorted.length - 1);
    }

    public void quickSort(int[] unSorted,int startIndex,int endIndex){
        if(startIndex < endIndex){


            int midValue = getMidValue(unSorted,startIndex,endIndex);

            int smallIndex = startIndex;
            int bigIndex = endIndex - 1;

            while (smallIndex < bigIndex){

                while(unSorted[smallIndex ++] < midValue){

                }
                while(unSorted[bigIndex --] > midValue){

                }
                if(smallIndex - 1 <= bigIndex + 1 ) {
                    swapTwoIndex(unSorted, smallIndex-1, bigIndex+1);
                }
            }
            bigIndex ++;
            swapTwoIndex(unSorted,bigIndex,endIndex);

            quickSort(unSorted,startIndex,bigIndex - 1);
            quickSort(unSorted,bigIndex + 1,endIndex);

        }
    }

    private int getMidValue(int[] unSorted, int startIndex, int endIndex) {
        int midIndex = (startIndex + endIndex)/2;
        if(unSorted[midIndex] < unSorted[startIndex]){
            swapTwoIndex(unSorted,midIndex,startIndex);
        }
        if(unSorted[endIndex] > unSorted[midIndex]){
            swapTwoIndex(unSorted,endIndex,midIndex);
        }else if(unSorted[endIndex] < unSorted[startIndex]){
            swapTwoIndex(unSorted,startIndex,endIndex);
        }
        return unSorted[endIndex];
    }

    private void swapTwoIndex(int[] array,int index1,int index2){
        int tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;
    }


    public void mergeSort(int[] unSorted){

        int[] tmpArray = new int[unSorted.length];

        mergeSort(unSorted,tmpArray,0,unSorted.length - 1);

    }

    public void mergeSort(int[] unSorted,int[] tmpArray,int startIndex,int endIndex){

        if(endIndex > startIndex){

            int mid = (startIndex + endIndex)/2;

            mergeSort(unSorted,tmpArray,startIndex,mid);

            mergeSort(unSorted,tmpArray,mid+1,endIndex);

            int tmpStart = startIndex;
            int tmpStart2 = mid + 1;
            int tmpArrayStart = startIndex;
            while(tmpStart <= mid && tmpStart2 <= endIndex ){

                if(unSorted[tmpStart] <= unSorted[tmpStart2]) {
                    tmpArray[tmpArrayStart++] = unSorted[tmpStart++];
                }else{
                    tmpArray[tmpArrayStart++] = unSorted[tmpStart2++];
                }
            }
            if(tmpStart <= mid ){
                while(tmpStart <= mid){
                    tmpArray[tmpArrayStart++] = unSorted[tmpStart++];
                }
            }
            if(tmpStart2 <= endIndex){
                while(tmpStart2 <= endIndex){
                    tmpArray[tmpArrayStart++] = unSorted[tmpStart2++];
                }
            }

            System.arraycopy(tmpArray,startIndex,unSorted,startIndex,endIndex - startIndex + 1);


        }

    }

}
